92. 反转链表 II

Similar Question

leading to the advanced question

25. K 个一组翻转链表

Solution Tips

方案一: 模拟 + 迭代

    reverseBetween(left, right) {

        const dummyHead = new Node(0);
        dummyHead.next = this.head;
        let count = 0;
        let cur = dummyHead;
        let slicePrev = null;
        let sliceNext = null;
        let sliceHead = null;
        let sliceTail = null;

        // 把 left 到 right slice 出来, 然后做反转之后再拼接回去?
        while (cur !== null) {
            if (count + 1 === left) {
                slicePrev = cur;
                sliceHead = cur.next;
            }

            if (count === right) {
                sliceTail = cur;
                sliceNext = cur.next;
                sliceTail.next = null;
            }

            cur = cur.next;
            count++
        }

        const newSliceHead = reverseList(sliceHead);
        const newSliceTail = sliceHead;

        // 拼接
        slicePrev.next = newSliceHead;
        newSliceTail.next = sliceNext;

        // 翻转 slice 链表
        function reverseList(head) {
            let cur = head;
            let prev = null;
            let next = null;

            while (cur !== null) {
                next = cur.next;
                cur.next = prev;

                prev = cur;
                cur = next;
            }

            return prev;
        }

        return dummyHead.next;
    }

方案二: 头插法

一边翻转, 然后不断的更新头引用

整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。

var reverseBetween = function(head, left, right) {
    // 设置 dummyNode 是这一类问题的一般做法
    const dummy_node = new ListNode(-1);
    dummy_node.next = head;
    let pre = dummy_node;
    for (let i = 0; i < left - 1; ++i) {
        pre = pre.next;
    }

    let cur = pre.next;
    for (let i = 0; i < right - left; ++i) {
        const next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummy_node.next;
};